论文分享|QuickSilver:任意域上的用于电路和多项式的可负担的高效零知识证明
论文名称:Yang K, Sarkar P, Weng C, et al. Quicksilver: Efficient and affordable zero-knowledge proofs for circuits and polynomials over any field
论文来源:Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021: 2986-3001.
论文整理 :济南大学信息科学与工程学院2021级硕士研究生孙奎恒
论文链接:https://dl.acm.org/doi/pdf/10.1145/3460120.3484556
现有较为流行的非交互式零知识证明方案(如,Groth16、Virgo等)都具有证明内存占用大,即可扩展性差的问题。这已成为了零知识证明系统可处理计算规模的重要瓶颈。这引起了广泛关注。有些方案尽管尝试解决可扩展性差的问题,如基于无隐私混淆电路的零知识协议、基于MPC-in-the-head的零知识证明协议等,但因为其在计算及通信效率方面的表现不是很理想,导致其无法进入实用。
近期提出的基于VOLE的零知识证明协议,通过类似“流式”的方式实现了高可扩展性零知识证明协议,但计算及通信效率仍较差。因此,本文提出了新的基于sVOLE的零知识证明方案“QuickSilver”,其通过VOLE的线性关系成功将证明电路中每个乘法门所需的VOLE实例降到1个,极大减少了整个协议的通信量。其次,其将基于VOLE的零知识证明协议首次应用于多项式,对于多个d阶多项式的证明,将协议所需VOLE关系降至n个,其中n为见证大小。
IT-MACs ( Information-Theoretic MACs )及sVOLE
信息论消息认证码(IT-MACs)可用于认证域
电路的零知识证明协议
2.1 协议的三个阶段
首先是预处理阶段(即,线下阶段),证明者
其次是线上阶段,首先便是对线值承诺。sVOLE具有加法同态的性质,因此加法门可以在本地进行计算,无需双方进行通信。这时只需对电路输入值及乘法门的输出值进行承诺,在本文的协议,对于
最后便是线上验证阶段,
2.2 乘法门的验证及证明
设双方已经拥有乘法门输入
且可以通过由验证者
2.3 扩展sVOLE及VOPE协议
扩展sVOLE用于协议中全局密钥
2.4 针对电路可满足性的零知识证明协议
这个协议具有完美完备性、错误为
用于多项式的零知识证明协议
3.1 证明内积
向量
因此可以将其变为线性关
这个对2阶多项式的证明过程只需发送
3.2 证明任意阶多项式
设多项式
其中,通过乘
3.3针对多项式的零知识证明协议
针对证明t个最多为d阶的n元多项式
这个协议具有完美完备性、错误为
实验结果与分析
4.1 基于电路的零知识证明协议
本文使用
在布尔电路中,QuickSilver与最先进的协议Wolverine相比,计算提高了6倍,通信提高了7倍;对于算术电路,与Wolverine和Mac'n'Cheese相比,QuickSilver协议在计算方面至少提高了7倍,在通信方面提高了3-4倍。
对于4核CPU的m5.2xlarge 类型的 Amazon EC2 机器,QuickSilver协议在布尔电路的计算速度为每秒 530 万到 730 万门,算术电路的速度为每秒 220 万到 300 万门。
4.2 基于多项式的零知识证明协议
在下面的所有实验中,对二进制域使用20 Mbps的网络带宽,对61比特域使用500 Mbps的网络带宽,并且始终使用单线程。
对于内积测试,证明者想要证明两个向量的内积
其次,对矩阵乘法进行测试,QuickSilver中基于多项式的零知识证明协议比基于电路的协议快31倍,通信比基于电路的协议少340倍。QuickSilver的证明体积仍然明显大于 Spartan 和 Virgo,但在执行时间和内存占用方面有优势。
对于证明解决基于格的问题(SIS),证明者证明其拥有向量
总结
本文通过利用IT-MAC的线性关系成功将乘法门所需sVOLE实例降至1个,相较先前方案在通信及执行效率方面都有较大提升,但通信量与验证时间仍与电路规模呈线性关系,无法做到如同ZK-SNARK等零知识证明方案的简洁性(即,次线性或恒定的证明体积与次线性的验证时间)。
基于VOLE的零知识证明协议无法实现非交互式,这使其应用范围大大缩小,但其高可扩展性,使其相比其它零知识证明方案可以更加容易地应用于如机器学习等大规模计算的证明及验证。
参考:SecurityLabUJN
分享仅供学习参考,若有不当,请联系我们处理。
END
热文推
3.论文分享|容忍恶意行为的联邦学习安全聚合方案——IEEE S&P 2023论文速览
荐4. 论文分享|Forward secure searchable encryption with keyed-block chain